﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0123_InorderTraversal : IAlgorithm
    {
        // 二叉树的中序遍历

        // 给定一个二叉树的根节点 root ，返回它的 中序 遍历。

        // 提示：
        //  树中节点数目在范围[0, 100] 内
        //  -100 <= Node.val <= 100

        // 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public IList<int> InorderTraversal(TreeNode root)
        {
            var res = new List<int>();
            Inorder(root, res);
            return res;
        }
        public void Inorder(TreeNode root, List<int> res)
        {
            if (root == null)
                return;
            Inorder(root.left, res);
            res.Add(root.val);
            Inorder(root.right, res);
        }

        public List<int> InorderTraversal1(TreeNode root)
        {
            if (root == null)
                return new List<int>();
            List<int> list = new List<int>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (root != null || stack.Count != 0)
            {
                while (root != null)
                {
                    stack.Push(root);
                    root = root.left;
                }
                if (stack.Count != 0)
                {
                    TreeNode node = stack.Pop();
                    list.Add(node.val);
                    root = node.right;
                }
            }
            return list;
        }
    }
}
